package com.hardy.leetcode;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * User: Ruijie Date: 2016/9/2
 */
public class BinaryTreeLevelOrderTraversalLi {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public static ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        Stack<ArrayList<Integer>> s=new Stack<ArrayList<Integer>>();
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        if(root!=null){
            q.offer(root);
            while(!q.isEmpty()){
                ArrayList<Integer> array=new ArrayList<Integer>();
                int size=q.size();
                while(size>0){
                    TreeNode node=q.poll();
                    array.add(node.val);
                    if(node.left!=null){
                        q.offer(node.left);
                    }
                    if(node.right!=null){
                        q.offer(node.right);
                    }
                    size--;
                }
                s.push(array);
            }
        }
        while(!s.empty()){
            res.add(s.pop());
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(3);
        root.left=new TreeNode(9);
        root.right=new TreeNode(20);
        root.right.left=new TreeNode(15);
        root.right.right=new TreeNode(7);
        System.out.println(levelOrderBottom(root));
    }
}
